// https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
package binarytree

func findMode(root *TreeNode) []int {
	var prev *TreeNode
	var maxCount, count int
	var modes []int

	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Left)

		if prev != nil {
			if node.Val == prev.Val {
				count++
			} else {
				count = 1
			}
		} else {
			count = 1
		}

		if count > maxCount {
			maxCount = count
			modes = []int{node.Val}
		} else if count == maxCount {
			modes = append(modes, node.Val)
		}

		prev = node
		inorder(node.Right)
	}

	inorder(root)
	return modes
}

// 这个函数的时间复杂度是 O(n)，其中 n 是树中的节点数，因为每个节点都被访问一次。
